package _16_设计;

import java.util.HashMap;
import java.util.Map;

// 使用前缀节点
public class _208_实现Trie前缀树 {

    // 根节点对象
    private final Node root;

    public _208_实现Trie前缀树() {
        root = new Node(null);
    }

    public void insert(String word) {

        int strLen = word.length();
        Node curNode = root;

        for (int i = 0; i < strLen; i++) {

            char curChar = word.charAt(i);
            Map<Character, Node> children = curNode.children;
            if (children == null) {
                children = new HashMap<>();
                curNode.children = children;
            }

            Node childrenNode = children.get(curChar);
            if (childrenNode == null) {
                childrenNode = new Node(curChar);
                children.put(curChar, childrenNode);
            }

            curNode = childrenNode;
        }
        // 设置最终数据
        curNode.word = word;
        curNode.isWord = true;
    }

    public boolean search(String word) {
        Node node = node(word);
        return node != null && node.isWord;
    }

    public boolean startsWith(String prefix) {
        return node(prefix) != null;
    }

    private Node node(String key) {
        // 根据字符串找到对应的节点
        if (root == null) return null;
        int strLen = key.length();

        Node curNode = root;
        for (int i = 0; i < strLen; i++) {
            char curChar = key.charAt(i);
            Map<Character, Node> children = curNode.children;
            if (children == null) return null;
            Node childrenNode = children.get(curChar);
            if (childrenNode == null) return null;
            curNode = childrenNode;
        }

        return curNode;
    }

    // 前缀树节点对象
    private static class Node {

        private String word;

        private boolean isWord;

        private Character character;

        private Map<Character, Node> children;

        public Node(Character character) {
            this.character = character;
        }
    }

}
